const int maxn = 500 + 5;
int dp[maxn][maxn];

class Solution {
public:
    int minDistance(string word1, string word2) {
        memset(dp, 0, sizeof(dp));
        int m = word1.size(), n = word2.size();
        if(word1[0] == word2[0])dp[0][0] = 1;
        for(int i = 1; i < n; i++)dp[0][i] = (word1[0] == word2[i] ? 1 : dp[0][i - 1]);
        for(int i = 1; i < m; i++)dp[i][0] = (word1[i] == word2[0] ? 1 : dp[i - 1][0]);
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                if(word1[i] == word2[j])dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return m + n - 2 * dp[m - 1][n - 1];
    }
};

/**
 * 2021.9.25
 * LCM问题
 */